As communications have progressed into the electronic domain, information has become easy to copy and disseminate. The prevalence of electronic communication has made for many productivity advances, and an increase in knowledge and information sharing. However, due to the ease of dissemination, there is an ever increasing need for privacy and authentication in electronic communications.
To retain privacy, the method of encrypting data using a key is very well known. In asymmetric key cryptographic protocols, computing devices, commonly referred to as correspondents, share a common secret key. This key must be agreed upon by the correspondents, and its secrecy maintained throughout the data communication.
Public key cryptographic protocols were first proposed in 1976 by Diffie-Hellman. A public-private key pair is created for each correspondent, with the public key made available to other parties, and the private key information maintained secret by the correspondent who will be the recipient of messages. Any message encrypted using the public key of a recipient can only be decrypted using the private key of that same recipient. The private key cannot be derived from the knowledge of the plaintext, ciphertext and public-key.
Cryptographic systems utilise protocols that are based on so called “hard” problems. These problems can be formulated quickly, but do not have efficient solution algorithms. Problems such as integer factorization and the discrete logarithm problem fall into this category.
Integer factorisation is the basis of a set of protocols known as RSA which uses, as a modulus n, the product of two large primes, p, q. A second modulus Φ is computed as (p−1)(q−1). A random integer e is selected so that 1<e<Φ and gcd(e,1)=1. A value d is selected so that 1<d<Φ and ed=1 mod Φ. A correspondent's public key is then (n,e) and the corresponding private key is d.
To send a message to a correspondent, the recipient's public key (n,e) is obtained and the message represented as an integer m in the interval [0,n−1]. The ciphertext c of message m is computed as c=me mod n and sent to the recipient correspondent. The recipient can decrypt and recover the plaintext from c by computing m=cd mod n.
The RSA algorithm is a deterministic algorithm requiring the selection of the large primes p, q. However, as integer factorisation techniques have improved, it has become necessary to use larger moduli, and, consequently, the computational efficiency has decreased.
The discrete log problem forms the basis for discrete log cryptographic systems that include Diffie Hellman key agreement protocols and ElGamal encryption and signature schemes. The problem is expressed as follows: given a finite cyclic group G of order n, a generator a of the group G, and an element β of the group G, find the integer x such that αx=β. Knowing the values α, β and the group G, it is considered infeasible to determine the integer x provided the number of elements n in G satisfies certain properties. In practical implementations, a random number generator is used to generate the random integer x, and the integer x is used as a private key by the correspondent. A corresponding public key is computed as αx and distributed publically to other correspondents. The public and private keys are used according to well known protocols to encrypt and decrypt messages sent between parties, to authenticate a message signed by one party using a private key, or to establish a common key between the parties by combining the public key of one party with the private key of another.
These protocols can be implemented practically in any group in which both the discrete logarithm problem is hard and the group operation is efficient. One example of such a group is the elliptic curve cyclic group defined over the finite field Fp composed of integers from 0 to p−1, where p is a prime number. The group elements are points lying on a defined elliptic curve and having coordinates that are elements of the underlying field. An elliptic curve group typically utilises an additive notation, rather than the multiplicative notation used above, so that a k-fold group operation of a point P requires the point P to be added k times and is written kP. A cryptographic system implemented using an elliptic curve group is known as an elliptic curve cryptographic system, or ECC. Other groups commonly used are multiplicative groups, such as the non-zero integers Fp and the corresponding k-fold group operation is denoted αk, where α is a generator of the group.
Although the discrete log problem is considered intractable, the security of the cryptographic system depends on the cryptographic strength of the random number x. A random number generator (RNG) is designed to provide cryptographically strong random numbers, but, due to malfunction, poor selection of a seed, or malicious tampering, the RNG may output relatively weak random numbers. This is a particular problem in constrained devices, such as cell phones and smart cards, where low cost implementations may not have sufficient entropy to provide a robust random number generator. As a result, publication of the public key may inadvertently disclose the corresponding private key, and, depending on the protocol implemented, may in turn yield information pertaining to other private keys used in the protocol.